Electronic devices for calculating the square root of a binary number are widely available. Such devices may employ either dedicated hardware, software or microcode. Irrespective of structure employed, most devices tend to use the direct calculational method, the Newton-Raphson iteration method or some variant of the Newton-Raphson method.
The direct method is the binary version of the decimal pencil-and-paper method. The direct method is slow due to the large number of iterations required to obtain the result. For example, the IEEE double precision data format with 53 significant bits requires 53 iterations to complete the calculation. In addition, each iterations requires many machine cycles.
The Newton-Raphson iteration method for the square root of a number N is based on the formula EQU x.sub.n+1 =(x.sub.n +N/x.sub.n)/2, (1)
where x.sub.n is the square root of the n.sup.th iteration and x.sub.n +1 is the square root of the (n+1).sup.st iteration. This method has an advantage over the direct method in that a fewer number of iterations are required. However, like the direct method, the Newton-Raphson method requires a relatively large number of machine cycles. This is due to the rather lengthy calculation for the quotient N/x.sub.n.
A modified versions of the Newton-Raphson method is based on the formula EQU x.sub.n+1 =x.sub.n (3-Nx.sup.2)/2 (2)
This modified version is much faster because it only requires multiplications and a subtraction and no long division. It should be noted that division by 2 in a binary operation is implemented by a shift operation, and therefore requires much less time than a long division. However, the modified equation converges to the reciprocal of the square root of N, thus requiring one long division at the end of the computation. The modified Newton-Raphson method also requires three (3) multiplication steps for each iteration. Attempts to improve on this method have focused on speeding up the multiplication operation. This is generally expensive because it necessitates additional hardware. Another problem with both the original and modified Newton-Raphson methods is that the number of iterations needed to obtain a stated precision is unknown. This prevents accurate prediction of the calculation time for a given problem.